# FirstDuplicate
# [2, 1, 5, 2, 3, 4, 5]

# 时间复杂度
# - 一个算法的执行时间随着输入的尺寸变化而产生的变化
# - O(n^2) n 是数组 array 的长度
# 
# 空间复杂度
# - 一个算法执行的时候，需要的内存空间，随着输入尺寸变化而产生的变化
# - O(1)
def firstDuplidate(array):
  for i in range(len(array)):
    value = array[i]

    for j in range(i + 1, len(array)):
      valueToCompare = array[j]

      if value == valueToCompare:
        return value

  return -1

# 时间复杂度 O(n)
# 空间复杂度 O(n) n - 是数组中个元素的个数
def first_duplicate(array):
  seen = set() # set 是一个天生就不能包含重复元素的结构

  for n in array:
    if n in seen: # 如何判断 set 中是否包含元素
      return n
    
    seen.add(n) # 向 set 中添加元素的方法
  
  return -1

print(first_duplicate([1, 2, 3, 4, 1]))